		#include "cursor.h"
		#include <stdlib.h>
		#include "fata.h"

		struct Node
		{
			ElementType Element;
			Position	Next;
		};

		struct Node CursorSpace[SpaceSize];

/* START: fig3_31.txt */
		static Position
		CursorAlloc()
		{
			Position P;
			P = CursorSpace[0].Next;
			CursorSpace[0].Next = CursorSpace[P].Next;
			return P;
		}

		static void
		CursorFree( Position P )
		{
			CursorSpace[P].Next = CursorSpace[0].Next;
			CursorSpace[0].Next = P;
		}
/* END */

		void
		InitializeCursorSpace()
		{
			int i;
			for ( i = 0; i < SpaceSize; i++ )
				CursorSpace[i].Next = i + 1;
			CursorSpace[SpaceSize - 1].Next = 0;
		}
		
		List
		MakeEmpty( List L )
		{
			if ( L != 0 )
                /* DeleteList( L ); The header is not free */
				DeleteList(L), CursorFree(L);
			L = CursorAlloc();
			if ( L == 0 )
				FataError( "Out of memory!" );
			CursorSpace[L].Next = 0;
			return L;
		}

/* START: fig3_32.txt */
        /* Return true if L is empty */
		int
		IsEmpty( const List L )
		{
			return CursorSpace[L].Next == 0;
		}
/* END */

/* START: fig3_33.txt */
        /* Return true if P is the last position in list L */
        /* Parameter L is unused in this implementation */
		int
		IsLast( const Position P, const List L )
		{
			(void)L;
			return CursorSpace[P].Next == 0;
		}
/* END */
	
/* START: fig3_34.txt */
        /* Return Position of X in L; 0 if not found */
        /* Uses a header node */
		Position
		Find( ElementType X, const List L )
		{
			Position P;
			P = CursorSpace[L].Next;
			while ( P != 0 && CursorSpace[P].Element != X )
				P = CursorSpace[P].Next;
			return P;
		}
/* END */

/* START: fig3_35.txt */
        /* Delete from a list */
        /* Assume that the position is legal */
        /* Assume use of a header node */
		void
		Delete( ElementType X, List L )
		{
			Position P, TmpCell;
			P = FindPrevious( X, L );
			if (!IsLast( P, L ))
			{
				TmpCell = CursorSpace[P].Next;
				CursorSpace[P].Next = CursorSpace[TmpCell].Next;
				CursorFree(TmpCell);
			}
		}
/* END */

		/* If X is not found, then Next field of returned value is 0 */
        /* Assumes a header */
		Position
		FindPrevious( ElementType X, const List L )
		{
			Position P;
			P = L;
			while (CursorSpace[P].Next != 0 && CursorSpace[ CursorSpace[P].Next ].Element != X)
				P = CursorSpace[P].Next;
			return P;
		}
/* END */

/* START: fig3_36.txt */
        /* Insert (after legal position P) */
        /* Header implementation assumed */
        /* Parameter L is unused in this implementation */
		void
		Insert( ElementType X, List L, Position P )
		{
			(void)L;
			Position TmpCell;
			TmpCell = CursorAlloc();
			if (TmpCell == 0)
				FataError( "Out of space" );
			CursorSpace[TmpCell].Element = X;
			CursorSpace[TmpCell].Next = CursorSpace[P].Next;
			CursorSpace[P].Next = TmpCell;
		}

		void
		DeleteList( List L )
		{
			Position P, Tmp;
			P = CursorSpace[L].Next;
			CursorSpace[L].Next = 0;
			while ( P != 0 )
			{
				Tmp = P;
				P = CursorSpace[Tmp].Next;
				CursorFree(Tmp);
			}
		}

		Position
		Header( const List L )
		{
			return L;
		}

		Position
		First( const List L )
		{
			return CursorSpace[L].Next;
		}

		Position
		Advance( const Position P )
		{
			return CursorSpace[P].Next;
		}

		ElementType
		Retrieve( const Position P )
		{
			return CursorSpace[P].Element;
		}
